<html>
<head><meta charset="utf-8"><title>HashMap zero capacity · general · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/index.html">general</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html">HashMap zero capacity</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="217200961"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217200961" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217200961">(Nov 18 2020 at 21:46)</a>:</h4>
<p>Does anyone else think it's surprising that HashMaps can report a capacity of zero even when they haven't freed their backing memory?</p>



<a name="217201586"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217201586" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Poliorcetics <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217201586">(Nov 18 2020 at 21:52)</a>:</h4>
<p>Do you have an example ?</p>



<a name="217201608"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217201608" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Poliorcetics <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217201608">(Nov 18 2020 at 21:52)</a>:</h4>
<p>Because I'm <em>very</em> surprised</p>



<a name="217202895"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217202895" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217202895">(Nov 18 2020 at 22:05)</a>:</h4>
<p>I think that might be possible if it's at full capacity and then you remove everything, leaving <code>DELETED</code> markers</p>



<a name="217202918"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217202918" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217202918">(Nov 18 2020 at 22:05)</a>:</h4>
<p>hashbrown reports capacity as a lower bound, <code>self.items + self.growth_left</code></p>



<a name="217203011"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217203011" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217203011">(Nov 18 2020 at 22:06)</a>:</h4>
<p>it's hard to reproduce, but I opened an issue and put instructions there: <a href="https://github.com/rust-lang/rust/issues/79178">https://github.com/rust-lang/rust/issues/79178</a></p>



<a name="217203108"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217203108" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217203108">(Nov 18 2020 at 22:07)</a>:</h4>
<p>the main difficulty is that there's no way to tell when it happens because no methods on HashMap let you distinguish between allocation/no-allocation</p>



<a name="217203155"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217203155" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217203155">(Nov 18 2020 at 22:07)</a>:</h4>
<p>but yeah it appears to be due to a combination of hash collisions and tombstones</p>



<a name="217203539"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217203539" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217203539">(Nov 18 2020 at 22:11)</a>:</h4>
<p>I spent a great deal of time tracking down a supposed memory leak :P</p>



<a name="217203809"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217203809" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217203809">(Nov 18 2020 at 22:12)</a>:</h4>
<p>for your code, would it be okay to add <code>if map.is_empty() { map.shrink_to_fit(); }</code>? (a no-op if it was already freed)</p>



<a name="217204004"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217204004" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217204004">(Nov 18 2020 at 22:14)</a>:</h4>
<p>Yeah I can use that as a workaround, but it does mean that the shrinking code doesn't work if hashbrown is unable to remove tombstones when you call <code>remove()</code></p>



<a name="217204023"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217204023" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217204023">(Nov 18 2020 at 22:14)</a>:</h4>
<p>I guess that happens if there was previously a collision?</p>



<a name="217204088"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217204088" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217204088">(Nov 18 2020 at 22:15)</a>:</h4>
<p>it's unclear exactly what conditions cause the capacity to deviate</p>



<a name="217204215"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217204215" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217204215">(Nov 18 2020 at 22:16)</a>:</h4>
<p>I'm worried about cases where the deviation becomes very large</p>



<a name="217204231"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217204231" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Diggsey <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217204231">(Nov 18 2020 at 22:16)</a>:</h4>
<p>but the map doesn't become completely empty</p>



<a name="217207615"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/HashMap%20zero%20capacity/near/217207615" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/HashMap.20zero.20capacity.html#217207615">(Nov 18 2020 at 22:49)</a>:</h4>
<p>I know that when you're growing, it does account for dead space in <code>reserve_rehash</code>:</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="n">full_capacity</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">bucket_mask_to_capacity</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">bucket_mask</span><span class="p">);</span><span class="w"></span>
<span class="w">        </span><span class="k">if</span><span class="w"> </span><span class="n">new_items</span><span class="w"> </span><span class="o">&lt;=</span><span class="w"> </span><span class="n">full_capacity</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="mi">2</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="c1">// Rehash in-place without re-allocating if we have plenty of spare</span>
<span class="w">            </span><span class="c1">// capacity that is locked up due to DELETED entries.</span>
<span class="w">            </span><span class="bp">self</span><span class="p">.</span><span class="n">rehash_in_place</span><span class="p">(</span><span class="n">hasher</span><span class="p">);</span><span class="w"></span>
</code></pre></div>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>